This invention relates to tools for the graphic presentation of data structures and to an application thereof for testing software performance.
Many of the prior art techniques mentioned in the next section are discussed in greater detail in the following publications:
[1] B. Beizer. Software testing techniques. Van Nostrand Reinhold, 1990.
[2] F. P. Brooks. The Mythical Man-Month: Essay on Software Engineering, Addison-Wesley, 1995.
[3] E. Buchnik and S. Ur. Compacting regression-suites on-the-fly. In Proceeding of the 4th Asia Pacific Software Engineering Conference, pages 385-394, December 1997.
[4] Michael Factor, Eithan Farchi and Shmuel Ur. Rigorous Testing Using Snapshot. Israeli Conference on the Theory of Computers and Systems (ISTCS), Herzelia, Israel, May 1997,
[5] C. Kaner. Software negligence and testing coverage, In Proceedings of the STAR 96: the Fifth International Conference, Software Testing, Analysis and Review, pages 299-327, June 1996.
[6] H. Levkowitz. Color Theory and Modeling for Computer Graphics, Visualization, and Multimedia Applications. Kluwer Academic Publishers, 1997.
[7] B. Marick The Craft of Software Testing, Subsystem testing Including Object-Based and Object-Oriented Testing. Prentice-Hall 1998.
[8] Y. S. Maarek, M. Jacovi, M. Shtalhaim, S. Ur, D. Zernik, and I. Z. Ben Shaul, WebCutter: A system for dynamic and tailorable site mapping, In the Proceedings of the Sixth International World Wide Web Conference, Santa-Clara, April 1997.
[9] S. Ur and A. Ziv Of-The-Shelf Vs. Custom Made Coverage models, Which is the One For You, STAR98
[10] U. Yahalom and A. Lichter. White Box Testing of C Programs, yearly software project, Technion.
[11] D. Zernik and G. Zodik. A graph management framework for 3D visualization. IBM Object Technology 97.
Data structures may be presented graphically as nodes interconnected by lines or edges. For example, a computer program can be presented graphically by means of many nodes each representative of a program block, interconnected by branches showing control flow between the various program blocks. Generally, graphical representation of such structures is prone to two problems. First, multiple coincident branches cannot be distinguished from one another. This makes it impossible to discern whether two nodes are joined by a single branch or several overlapping branches. Secondly, even if this problem is overcome, it remains impossible to trace a path which spans several nodes, since all edges appear identical. These drawbacks are manifest in graphical tools for program testing.
Testing is one of the biggest problems of the software industry. It has been shown that the cost of testing is usually between 40-80% of the development process as compared with less than 20% for the coding itself. The practice of letting the users find the bugs and fixing them in the next release, is becoming dangerous and costly for three main reasons: reputation and brand-name are harmed; replacing the software can be very costly when there is a large installation base; and there is the danger of litigation if the software error caused harm to the user. Therefore, thorough testing is required and care must be exercised to ensure that testing resources are used efficiently.
Modern software products are increasingly complex and typically offer literally thousands of options. In order to test software in such a manner that bugs can be reliably detected, it is necessary to run the software through each of the possible control paths. In fact, since bugs can be a function of the order in which options are selected, proper testing requires that the order of selecting options be varied accordingly and that the control flow be observed.
The main technique for demonstrating that the testing has been thorough is called test coverage analysis. Simply stated, software testing requires that there be created, in some systematic fashion, a large and comprehensive list of tasks and that some check be initiated to ensure that each task is covered in the testing phase. Coverage can help in monitoring the quality of testing, in creating tests for areas that have not been tested before, and with. forming small, yet comprehensive, regression suites.
Coverage is defined as any metric of completeness with respect to test selection criteria [1]. Many such metrics have been suggested in the past [1] [5], of which statement coverage is the most common. The statement coverage model measures against a set of tests, for each statement, if the statement were executed by one of the tests. When using any coverage model, a metric is created against which the quality and completeness of the testing is measured.
The most commonly used coverage metrics, such as statement coverage and branch coverage are based on the control flow of the program. However, many other metrics exist. Some coverage metrics are based on the data flow of variables, like define-use [1], while others are based not on the program code but on the inputs or the specifications [10].
Assessing coverage results is a difficult task. One of the main problems is that there are many details and, as a result, it is hard xe2x80x9cto see the wood for the treesxe2x80x9d. For example, it may occur that many statements are not covered owing to a single cause, but superficial analysis will show only a list of statements not covered without showing their interrelationship. Amongst the most commonly used coverage models are statement coverage and branch coverage, whilst more recently proposed is forward path as described by Factor et al. [4]. All of these models define criteria for dealing with the control flow of the program.
Coverage results, whether of branch coverage, statement coverage or path coverage, produce a vast amount of information. Known methods for presenting this information are in textual form, such as a list or table. These suffer from several drawbacks. First, global analysis of the coverage information is difficult since textual information can cover many pages. Furthermore, presenting a one to many relation is cumbersome in textual format, as basic blocks can only be presented one after the other. As a result, such approaches militate against an intuitive perception of the flow of control.
It is therefore known to use two-dimensional graphical images to represent coverage results so as to provide a more intuitive global view than can be achieved textually. McCabe and Associates, Inc. of Columbia, U.S.A. offer a software testing tool known as xe2x80x9cVisual Testing Toolkitxe2x80x9d allowing two-dimensional graphical display of a structure chart of a system. Modules are shown as blocks which are interconnected via control paths. The modules are color-coded based on whether or not they have been tested so that untested areas may be quickly identified. Viewing the entire control graph allows points of interest, such as the most frequently used basic block etc., to be pinpointed and provides a clear view of the flow of control during the program""s execution. Those paths in the program which have yet to be tested are shown both graphically and in the form of a listing.
Nontrivial programs have large and complex control graphs. Presenting coverage information as a graph in two dimensions not only requires substantial space but might become incomprehensible due to many intersecting edges. Both factors militate against achieving an intuitive global view.
FIG. 1 shows a 2-D graphical representation of a segment of a control graph describing a xe2x80x9ccasexe2x80x9d statement. It will be appreciated that this segment is but one small component of the complete control graph, and yet requires significant area for its effective display. Clearly, to display a 2-D representation of the entire control graph would require a display medium of such large size, that it cannot be done.
It thus emerges that notwithstanding the advantages of displaying coverage results as a 2-D control graph, the effective use of 2-D is limited to the display of sub-components of the control graph and is not suited to the display of the entire control graph. Seeing that the very reason for using a graphical, rather than a textual, representation is to allow the coverage results to be displayed in their entirety for instant assimilation by the user, this limitation is a major drawback.
Although presenting coverage results graphically allows information to be imparted much more compactly than can be done textually, it does not in itself allow easy differentiation of multiple paths in the control graph. It is difficult to show path coverage graphically for several reasons. First, multiple paths typically pass through a single edge of the control graph. If every path has a different marking, then an edge through which several paths pass, needs to have an equal number of distinguishing characteristics. Also, a lot of information must be presented in a manner which can easily be assimilated by the user without the need to plow through many pages of information.
It is therefore an object of the invention to provide a method for graphically displaying control data of a computer program having multiple paths in such a manner than the paths can be visually distinguished.
To this end there is provided, in accordance with a broad aspect of the invention, a computer-implemented method for displaying data representative of at least two edges branching between a pair of nodes so as to allow the edges to be separately identifiable, the method comprising the steps of:
(a) assigning different display attributes to the edges so that the edges can be visually distinguished, and
(b) displaying said data structure graphically in 3-D.
Such a method finds particular application for graphically displaying execution paths of a computer program component having multiple execution paths, which are represented by the edges, wherein prior to step (a) there is included the step of:
processing the computer program component so as to derive a data structure containing said nodes being representative of all basic blocks thereof, said edges representing lines connecting said nodes, and said execution paths being traversed during operation of the computer program component.
The use of three dimensions almost eliminates the chance of edge intersection and enables displaying more information in one frame. More particularly, a global overview of the coverage information of a procedure, which contains many details, can be presented in one view. This enables areas of interest to be pinpointed with ease. It further provides the ability to display path information, thus presenting the flow of control in a graphical way.